package date0423;

public class Solution {
	public static void main(String[] args) {
		Solution solution = new Solution();
		Integer[] t1 = { 8, 8, 7, 9, 2, 1, 1, 1, 1, 4, 7 };
		Integer[] t2 = { 8, 9, 2 };
		Tree tree = new Tree();
		Tree tree2 = new Tree();
		TreeNode n1 = tree.createBinTree(t1);
		TreeNode n2 = tree2.createBinTree(t2);
		// tree2.preOrderTraver(n1);
		System.out.println(solution.HasSubtree(n1, n2));

	}

	/*
	 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，
	 * 偶数和偶数之间的相对位置不变。
	 */
	public void reOrderArray(int[] array) {
		int arr[] = new int[array.length];
		int i = 0;
		int j = array.length - 1;
		int m = 0, n = j;
		while ((i <= array.length - 1) && (j >= 0)) {
			if ((array[i] % 2) == 1) {// 为奇数
				arr[m++] = array[i];
			}
			if ((array[j] % 2) == 0) {
				arr[n--] = array[j];
			}
			i++;
			j--;
		}
		while ((i <= array.length - 1)) {
			if ((array[i] % 2) == 1) {// 为偶数
				arr[m++] = array[i];
			}
			i++;
			j--;
		}
		while (j >= 0) {
			if ((array[j] % 2) == 0) {
				arr[n--] = array[j];
			}
			i++;
			j--;
		}

		for (int k = 0; k < arr.length; k++) {
			array[k] = arr[k];
		}

	}

	/*
	 * 输入一个链表，输出该链表中倒数第k个结点。
	 */
	public ListNode FindKthToTail(ListNode head, int k) {
		ListNode p, pre;
		p = head;
		pre = head;
		int a = k;
		int count = 0;
		while (p != null) {
			p = p.next;
			count++;
			if (k <= 0) {
				pre = pre.next;
			}
			k--;
		}
		if (count < a)
			return null;
		return pre;
	}

	/*
	 * 输入一个链表，反转链表后，输出链表的所有元素。
	 */
	public ListNode ReverseList(ListNode head) {
		ListNode pre = null;
		ListNode next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

	/*
	 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
	 */

	public ListNode Merge(ListNode list1, ListNode list2) {
		if (list1 == null)
			return list2;
		if (list2 == null)
			return list1;
		if (list1.val < list2.val) {
			list1 = Merge(list1.next, list2);
			return list1;
		} else {
			list2 = Merge(list1, list2.next);
			return list2;
		}

	}

	/*
	 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
	 */
	public boolean HasSubtree(TreeNode root1, TreeNode root2) {
		boolean result = false;
		if (root1 != null && root2 != null) {
			if (root1.val == root2.val) {
				result = hasSubTree2(root1, root2);
			}
			if (result == false) {
				result = HasSubtree(root1.left, root2);
				if (result == false) {
					result = HasSubtree(root1.right, root2);
				}
			}
		}
		return result;
	}

	boolean hasSubTree2(TreeNode root1, TreeNode root2) {
		if (root1 == null)
			return false;
		if (root2 == null)
			return true;
		if (root1.val != root2.val)
			return false;
		return hasSubTree2(root1.left, root2.left) && hasSubTree2(root1.right, root2.right);
	}
}
